#include <bits/stdc++.h>

// 爬楼梯
// 假设你正在爬楼梯，每次你可以爬1或2个台阶
// 你有多少种不同的方法可以爬到n层
// 测试链接 : https://leetcode.cn/problems/climbing-stairs/
// 这个测试的数据量太小，并且不牵扯取模的事情
// 所以矩阵快速幂看不出优势

class Solution 
{
public:
    // 时间复杂度O(logn)，矩阵快速幂的解法
    int climbStairs(int n)
    {
        if(n <= 1) return 1;
        vector<vector<long>> start = {{1, 1}};
        vector<vector<long>> base = {
            {1, 1},
            {1, 0}
        };
        vector<vector<long>> ans = multiply(start, power(base, n - 1));
        return ans[0][0];
    }

	// 矩阵相乘
	// a的列数一定要等于b的行数
    vector<vector<long>> multiply(const vector<vector<long>>& a,  const vector<vector<long>>& b)
    {
        int m = a.size();
        int n = b[0].size();
        int k = a[0].size();
        vector<vector<long>> ans(m, vector<long>(n));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                for(int c = 0; c < k; ++c)
                {
                    ans[i][j] += a[i][c] * b[c][j];
                }
            }
        }
        return ans;
    }

    // 矩阵快速幂
    vector<vector<long>> power(vector<vector<long>>& m, int p)
    {
        int n = m.size();
        vector<vector<long>> ans(n, vector<long>(n));
        for(int i = 0; i < n; ++i) ans[i][i] = 1;
        while(p)
        {
            if(p & 1) ans = multiply(ans, m);
            m = multiply(m, m);
            p >>= 1;
        }
        return ans;
    }
};